package com.caochenlei.graph;

public class Cycle {
    private boolean[] marked;                   //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean hasCycle;                   //记录图中是否有环

    public Cycle(Graph G) {
        this.marked = new boolean[G.size()];    //初始化marked数组
        this.hasCycle = false;                  //初始化hasCycle变量

        for (int v = 0; v < G.size(); v++) {
            if (!marked[v]) {                   //判断当前v顶点有没有被搜索过
                dfs(G, v, v);                   //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
    }

    private void dfs(Graph G, int v, int u) {   //v代表当前顶点，u代表当前顶点的父顶点(这里的父顶点表示dfs遍历顺序中的父顶点)
        marked[v] = true;                       //把v顶点标识为已搜索
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                dfs(G, w, v);                   //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            } else if (w != u) {                //如果存在某个邻接的顶点已被标记为访问状态，且这个顶点不是当前顶点的父顶点
                hasCycle = true;                //那么这个图就是存在回路的
            }
        }
    }

    //判断当前无向图G中是否有环
    public boolean hasCycle() {
        return hasCycle;
    }
}
